<?php

namespace maotool\util;


use maotool\log\Console;
use maotool\object\ObjUtil;
use maotool\object\StrUtil;

/**
 * 树结构工具
 */
class TreeUtil
{

    /**
     * 数组转树结构
     * @param $list
     * @param $config
     * @return array
     */
    public static function listToTree($list, $config = [
        "id" => "id", // id字段别名
        "name" => null, // 名称字段别名
        "parent_id" => "parent_id", // 父节点字段别名
        "children" => "children", // 子节点字段别名
        "full_id" => null, // 完整id字段别名
        "full_name" => null, // 完整名称字段别名
        "level" => null, // 层级字段别名
        "init_level" => null, // 初始化的层级数
        "max_level" => null, // 最大的层级数
    ])
    {
        // 初始化参数
        $config['id'] = isset($config['id']) ? $config['id'] : "id";
        $config['parent_id'] = isset($config['parent_id']) ? $config['parent_id'] : "parent_id";
        $config['children'] = isset($config['children']) ? $config['children'] : "children";
        // 新建映射关系
        $map = [];
        foreach ($list as &$item) {
            // 跳过开头的上级节点
            if (isset($config['level']) && isset($config['init_level']) && isset($item[$config['level']])) {
                if ($item[$config['level']] < $config['init_level']) {
                    continue;
                }
            }
            $map[$item[$config["id"]]] = &$item;
        }
        // 树数据
        $tree = [];
        foreach ($list as &$item) {
            // 跳过开头的上级节点
            if (isset($config['level']) && isset($config['init_level']) && isset($item[$config['level']])) {
                if ($item[$config['level']] < $config['init_level']) {
                    continue;
                }
            }
            // 获取上级节点
            $parentId = null;
            if (isset($map[$item[$config["parent_id"]]])) {
                $parentId = $item[$config["parent_id"]];
            } else {
                // 通过完整id字段 查找上级节点 补充缺省上级数据
                if (isset($config["full_id"]) && isset($item[$config["full_id"]])) {
                    $ids = explode(",", $item[$config["full_id"]]);
                    foreach ($ids as $id) {
                        if ($item[$config["id"]] != $id && isset($map[$id])) {
                            $parentId = $id;
                        }
                    }
                }
            }
            // 判断上级节点是否存在 不存在则添加到顶级节点
            if (isset($parentId)) {
                // 添加到子节点
                if (!isset($map[$parentId][$config["children"]])) {
                    $map[$parentId][$config["children"]] = [];
                }
                $map[$parentId][$config["children"]][] = &$item;
            } else {
                $tree[] = &$item;
            }
        }
        unset($item);
        return self::recursion($tree, function ($data, $next, $node) use ($config) {
            foreach ($data as &$item) {
                if (isset($config["level"])) {
                    $item[$config["level"]] = $node["level"];
                }
                if (isset($item[$config["children"]])) {
                    if (isset($config["level"]) && isset($config["max_level"])) {
                        if ($node["level"] + 1 > $config["max_level"]) {
                            unset($item[$config["children"]]);
                        } else {
                            $item[$config["children"]] = $next($item[$config["children"]], $next);
                        }
                    } else {
                        $item[$config["children"]] = $next($item[$config["children"]], $next);
                    }
                }
            }
            return $data;
        });
    }

    /**
     * 树结构转数组
     * @param $tree
     * @param $config
     * @return array
     */
    public static function treeToList($tree, $config = [
        "children" => "children",
        "unset_children" => true,
    ])
    {
        $listHandle = function ($tree, $config, $listHandle) {
            $list = [];
            foreach ($tree as $item) {
                if (isset($item[$config["children"]])) {
                    $children = $item[$config["children"]];
                    if (isset($config["unset_children"]) && $config["unset_children"]) {
                        unset($item[$config["children"]]);
                    }
                } else {
                    $children = null;
                }
                $list[] = $item;
                if (is_array($children)) {
                    $list = array_merge($list, $listHandle($children, $config, $listHandle));
                }
            }
            return $list;
        };
        return $listHandle($tree, $config, $listHandle);
    }

    /**
     * 查找树结构中指定节点
     * @param $tree
     * @param $self
     * @param $config
     * @return mixed
     */
    public static function findTreeBySelf($tree, $self, $config = [
        "id" => "id",
        "children" => "children",
    ])
    {
        $listHandle = function ($tree, $self, $config, $listHandle) {
            foreach ($tree as $item) {
                if ($item[$config["id"]] == $self[$config["id"]]) {
                    return $item;
                }
                if (is_array($item[$config["children"]])) {
                    $children = $listHandle($item[$config["children"]], $self, $config, $listHandle);
                    if (!is_null($children)) {
                        return $children;
                    }
                }
            }
            return null;
        };
        return $listHandle($tree, $self, $config, $listHandle);
    }

    /**
     * 查找列表结构的指定节点
     * @param $list
     * @param $self
     * @param $config
     * @return array
     */
    public static function findListBySelf($list, $self, $config = [
        "id" => "id",
        "parent_id" => "parent_id",
        "children" => "children",
    ])
    {
        $tree = TreeUtil::listToTree($list, $config);
        return TreeUtil::treeToList(self::findTreeBySelf($tree, $self, $config));
    }

    /**
     * 查找树结构中指定节点
     * @param $tree
     * @param $self
     * @param $config
     * @return mixed
     */
    public static function findTreeByChildren($tree, $self, $config = [
        "id" => "id",
        "parent_id" => "parent_id",
        "children" => "children",
    ])
    {
        $listHandle = function ($tree, $self, $config, $listHandle) {
            foreach ($tree as $item) {
                if ($item[$config["id"]] == $self[$config["id"]]) {
                    if (is_array($item[$config["children"]])) {
                        return $item[$config["children"]];
                    } else {
                        return [];
                    }
                }
                if (is_array($item[$config["children"]])) {
                    $children = $listHandle($item[$config["children"]], $self, $config, $listHandle);
                    if (!is_null($children)) {
                        return $children;
                    }
                }
            }
            return null;
        };
        return $listHandle($tree, $self, $config, $listHandle) ?: [];
    }

    /**
     * 查找列表结构的指定节点的下级节点
     * @param $list
     * @param $self
     * @param $config
     * @return array
     */
    public static function findListByChildren($list, $self, $config = [
        "id" => "id",
        "parent_id" => "parent_id",
        "children" => "children",
    ])
    {
        $tree = TreeUtil::listToTree($list, $config);
        return TreeUtil::treeToList(self::findTreeByChildren($tree, $self, $config));
    }

    /**
     * 查找树结构中指定节点的父节点
     * @param $tree
     * @param $self
     * @param $config
     * @return mixed
     */
    public static function findTreeByParent($tree, $self, $config = [
        "id" => "id",
        "name" => null,
        "parent_id" => "parent_id",
        "children" => "children",
        "full_id" => null,
    ])
    {
        $list = TreeUtil::treeToList($tree, $config);
        if (isset($config['full_id']) && isset($self[$config['full_id']])) {
            foreach (StrUtil::split($self[$config['full_id']], ",") as $id) {
                if ($self[$config["id"]] != $id) {
                    foreach ($list as $item) {
                        if ($item[$config["id"]] == $id) {
                            return $item;
                        }
                    }
                }
            }
        } else {
            foreach ($list as $item) {
                if (isset($item[$config["id"]])) {
                    if ($item[$config["id"]] == $self[$config["parent_id"]]) {
                        return $item;
                    }
                }
            }
        }
        return null;
    }

    /**
     * 获取树节点的最大的深度
     * @param array $tree 树结构数据
     * @param array $config 配置参数
     * @return int 返回最大的深度
     */
    public static function getMaxDepth($tree, $config = [
        "id" => "id",
        "children" => "children",
    ])
    {
        // 初始化最大深度为0
        $maxDepth = 0;

        // 使用递归函数遍历树
        self::recursionEach($tree, function ($item, $node) use (&$maxDepth, $config) {
            // 如果当前节点的层级大于已知最大深度，则更新最大深度
            // 注意：层级从0开始计数，所以实际深度是 level + 1
            if ($node['level'] + 1 > $maxDepth) {
                $maxDepth = $node['level'] + 1;
            }
        }, $config);

        return $maxDepth;
    }

    /**
     * 查找树结构中指定节点的所有父节点
     * @param $tree
     * @param $self
     * @param $config
     * @return array
     */
    public static function findTreeByParents($tree, $self, $config = [
        "id" => "id",
        "parent_id" => "parent_id",
        "children" => "children",
        "full_id" => null,
    ])
    {
        $parents = [];
        $list = TreeUtil::treeToList($tree, $config);
        if (isset($config['full_id']) && isset($self[$config['full_id']])) {
            foreach (ArrayUtil::flip(StrUtil::split($self[$config['full_id']], ",")) as $id) {
                if ($self[$config["id"]] != $id) {
                    foreach ($list as $item) {
                        if ($item[$config["id"]] == $id) {
                            $parents[] = $item;
                        }
                    }
                }
            }
            return $parents;
        } else {
            $index = $self;
            while (true) {
                $isTop = true;
                foreach ($list as $item) {
                    if (isset($item[$config["id"]])) {
                        if ($item[$config["id"]] === $index[$config["parent_id"]]) {
                            $index = $item;
                            $parents[] = $item;
                            $isTop = false;
                        }
                    }
                }
                if ($isTop) {
                    return $parents;
                }
            }
        }
    }

    /**
     * 获取树结构单个列数据
     * @param $tree
     * @param $column
     * @param $config
     * @return array
     */
    public static function treeToColumn($tree, $column, $config = [
        "id" => "id",
        "parent_id" => "parent_id",
        "children" => "children",
    ])
    {
        $list = self::treeToList($tree, $config);
        $columns = [];
        foreach ($list as $item) {
            $columns[] = $item[$column];
        }
        return $columns;
    }

    /**
     * 查找包含字段值的数据
     * @param $tree
     * @param $key
     * @param $value
     * @param $config
     * @return mixed|null
     */
    public static function findOne($tree, $key, $value, $config = [
        "id" => "id",
        "parent_id" => "parent_id",
        "children" => "children",
    ])
    {
        $listHandle = function ($tree, $key, $value, $config, $listHandle) {
            foreach ($tree as $item) {
                if ($item[$key] == $value) {
                    return $item;
                }
                if (is_array($item[$config["children"]])) {
                    $children = $listHandle($item[$config["children"]], $key, $value, $config, $listHandle);
                    if (!is_null($children)) {
                        return $children;
                    }
                }
            }
            return null;
        };
        return $listHandle($tree, $key, $value, $config, $listHandle);
    }

    /**
     * 查找包含字段值的数据
     * @param $tree
     * @param $key
     * @param $value
     * @param $config
     * @return array
     */
    public static function findAll($tree, $key, $value, $config = [
        "id" => "id",
        "parent_id" => "parent_id",
        "children" => "children",
    ])
    {
        $list = [];
        $listHandle = function ($tree, $key, $value, $config, $listHandle) use (&$list) {
            foreach ($tree as $item) {
                if ($item[$key] == $value) {
                    $list[] = $item;
                }
                if (is_array($item[$config["children"]])) {
                    $listHandle($item[$config["children"]], $key, $value, $config, $listHandle);
                }
            }
        };
        $listHandle($tree, $key, $value, $config, $listHandle);
        return $list;
    }

    /**
     * 下级全部节点
     * @return array
     */
    public static function nextChildrenAll($tree, $config = [
        "id" => "id",
        "parent_id" => "parent_id",
        "children" => "children",
    ])
    {
        $nextTree = [];
        foreach ($tree as $treeItem) {
            if (isset($treeItem['children']) && is_array($treeItem['children'])) {
                foreach ($treeItem['children'] as $item) {
                    $nextTree[] = $item;
                }
            }
        }
        return $nextTree;
    }

    /**
     * 递归处理树形数据的核心方法
     * @param array $paramOrTree 待处理的数据
     * @param callable $mainNext 处理函数
     * @param array $node 节点信息，包含：
     *   - level: 当前层级
     *   - top: 是否为顶层节点
     *   - parent: 父节点引用
     *   - parents: 所有父节点数组
     * @return mixed 处理后的结果
     */
    public static function recursion($paramOrTree, $mainNext, $node = ["level" => 0, "top" => true, "parent" => null, "parents" => []])
    {
        return $mainNext($paramOrTree, function ($paramOrTree, $parent) use ($mainNext, $node) {
            $node["level"] = $node["level"] + 1;
            $node["top"] = false;
            $node["parent"] = $parent;
            $node["parents"] = ArrayUtil::merge($node["parents"], [$parent]);
            return self::recursion($paramOrTree, $mainNext, $node);
        }, $node);
    }

    /**
     * 遍历树形结构中的每个节点并执行回调函数
     * @param array $tree 树形结构数据
     * @param callable $func 回调函数，接收(item, node)参数
     * @param array $config 配置参数：
     *   - id: 节点ID字段名，默认为"id"
     *   - parent_id: 父节点ID字段名，默认为"parent_id"
     *   - children: 子节点字段名，默认为"children"
     * @return array
     */
    public static function recursionEach($tree, $func, $config = [
        "children" => "children",
    ])
    {
        $treeHandle = function (&$tree, $treeHandle, $node = ["level" => 0, "top" => true, "parent" => null, "parents" => []]) use ($func, $config) {
            foreach ($tree as &$item) {
                $func($item, $node);
                if (array_key_exists($config["children"], $item) && is_array($item[$config["children"]])) {
                    $treeHandle($item[$config["children"]], $treeHandle, [
                        "parent" => $item,
                        "parents" => ArrayUtil::merge($node["parents"], [$item]),
                        "level" => $node["level"] + 1,
                        "top" => false,
                    ]);
                }
            }
        };
        $treeHandle($tree, $treeHandle);
        return $tree;
    }

}